using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection.Emit;
using System.Reflection;
using System.IO;
using System.Diagnostics;

namespace DynCalc
{
    class ParseException : Exception
    {
        public ParseException(string message)
            : base(message)
        {
        }
    }

    static class Expression
    {
        private static Queue<MathOpOrVal> queue;

        public static Queue<MathOpOrVal> InfixToPostfix(string expr)
        {
            if (expr == null)
                throw new ArgumentNullException();

            if (expr == "")
                throw new ArgumentException("Empty infix expression");

            queue = new Queue<MathOpOrVal>();

            StringReader sr = new StringReader(expr);
            Stack<char> stack = new Stack<char>();

            do
            {
                char c = (char)sr.Read();

                if (char.IsWhiteSpace(c))
                {
                    continue;
                }
                else if (char.IsDigit(c))
                {
                    int val = (int)(c - '0');

                    char p = (char)sr.Peek();
                    while (p >= '0' && p <= '9')
                    {
                        val = val * 10 + (int)(sr.Read() - '0');
                        p = (char)sr.Peek();
                    }

                    Append(val);
                }
                else if (c == '(')
                {
                    stack.Push(c);
                }
                else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%')
                {
                    bool repeat;
                    do
                    {
                        repeat = false;
                        if (stack.Count == 0)
                            stack.Push(c);
                        else if (stack.Peek() == '(')
                            stack.Push(c);
                        else if (Precedence(c) > Precedence(stack.Peek()))
                            stack.Push(c);
                        else
                        {
                            Append(stack.Pop());
                            repeat = true;
                        }
                    } while (repeat);
                }
                else if (c == ')')
                {
                    bool ok = false;
                    while (stack.Count > 0)
                    {
                        char p = stack.Pop();
                        if (p == '(')
                        {
                            ok = true;
                            break;
                        }
                        else
                            Append(p);
                    }

                    if (!ok)
                        throw new ParseException("Unbalanced parentheses.");
                }
                else
                    throw new ParseException("Invalid character encountered: " + c);
            } while (sr.Peek() != -1);

            while (stack.Count > 0)
            {
                char p = stack.Pop();
                if (p == '(')
                    throw new ParseException("Unbalanced parentheses.");
                Append(p);
            }

            return queue;
        }

        private static void Append(char c)
        {
            switch (c)
            {
                case '+':
                    queue.Enqueue(new MathOpOrVal(MathOp.Add));
                    break;
                case '-':
                    queue.Enqueue(new MathOpOrVal(MathOp.Sub));
                    break;
                case '*':
                    queue.Enqueue(new MathOpOrVal(MathOp.Mul));
                    break;
                case '/':
                    queue.Enqueue(new MathOpOrVal(MathOp.Div));
                    break;
                case '%':
                    queue.Enqueue(new MathOpOrVal(MathOp.Mod));
                    break;
                default:
                    throw new ParseException("Parser error.");
            }
        }

        private static void Append(int v)
        {
            queue.Enqueue(new MathOpOrVal(v));
        }

        private static int Precedence(char c)
        {
            switch (c)
            {
                case '*':
                case '/':
                case '%':
                    return 2;
                case '+':
                case '-':
                    return 1;
                default:
                    throw new Exception(); //should not happen
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Dynamic calculator");
            Console.WriteLine("------------------");
            Console.WriteLine();

            Console.Write("Expression: ");
            string expr = Console.ReadLine();

            Queue<MathOpOrVal> q = Expression.InfixToPostfix(expr);

            Console.WriteLine();
            Console.Write("Postfix representation: ");
            Print(q);

            Console.WriteLine();
            Console.WriteLine("Tree representation:");
            TreeNode tree = ToTree(q);
            Print(tree);

            Console.WriteLine();
            Console.Write("Dynamic calculation: ");
            Console.WriteLine("Result = {0}", Execute(tree));
        }

        static void Print(Queue<MathOpOrVal> q)
        {
            foreach (MathOpOrVal mv in q)
                Console.Write(mv + " ");
            Console.WriteLine();
        }

        public static TreeNode ToTree(Queue<MathOpOrVal> q)
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();

            foreach (MathOpOrVal mv in q)
            {
                if (mv.Value != null)
                    stack.Push(new TreeNode(mv.Value.Value));
                else
                {
                    TreeNode right = stack.Pop();
                    TreeNode left = stack.Pop();
                    stack.Push(new TreeNode(mv.Op.Value, left, right));
                }
            }

            return stack.Pop();
        }

        private static void Print(TreeNode tree)
        {
            PrintTree(tree, "");
        }

        private static void PrintTree(TreeNode tree, string spacing)
        {
            if (tree.Op != null)
            {
                Console.WriteLine(spacing + "+" + tree.Op);
                PrintTree(tree.Left, spacing + " ");
                PrintTree(tree.Right, spacing + " ");
            }
            else
                Console.WriteLine(spacing + tree.Value);
        }

        private static int i = 0;

        public static int Execute(TreeNode root)
        {
            DynamicMethod method = new DynamicMethod(
                "Exec_" + i++,
                typeof(int),
                new Type[] { },
                typeof(Program).Module
            );

            ILGenerator gen = method.GetILGenerator();

            Stack<MathOpOrVal> stack = new Stack<MathOpOrVal>();
            BuildStack(stack, root);

            while (stack.Count > 0)
            {
                MathOpOrVal e = stack.Pop();
                if (e.Op != null)
                {
                    switch (e.Op)
                    {
                        case MathOp.Add:
                            Debug.WriteLine("add");
                            gen.Emit(OpCodes.Add);
                            break;
                        case MathOp.Sub:
                            Debug.WriteLine("sub");
                            gen.Emit(OpCodes.Sub);
                            break;
                        case MathOp.Mul:
                            Debug.WriteLine("mul");
                            gen.Emit(OpCodes.Mul);
                            break;
                        case MathOp.Div:
                            Debug.WriteLine("div");
                            gen.Emit(OpCodes.Div);
                            break;
                        case MathOp.Mod:
                            Debug.WriteLine("mod");
                            gen.Emit(OpCodes.Rem);
                            break;
                    }
                }
                else
                {
                    Debug.WriteLine("ldc " + e.Value.Value);
                    gen.Emit(OpCodes.Ldc_I4, e.Value.Value);
                }
            }

            gen.Emit(OpCodes.Ret);

            return (int)method.Invoke(
                  null,
                  BindingFlags.ExactBinding,
                  null,
                  new object[] { },
                  null
               );

        }

        private static void BuildStack(Stack<MathOpOrVal> stack, TreeNode root)
        {
            if (root.Op != null)
            {
                MathOpOrVal e = new MathOpOrVal(root.Op.Value);
                stack.Push(e);
                BuildStack(stack, root.Right);
                BuildStack(stack, root.Left);
            }
            else
            {
                MathOpOrVal e = new MathOpOrVal(root.Value.Value);
                stack.Push(e);
            }
        }
    }

    internal class MathOpOrVal
    {
        public MathOp? Op;
        public int? Value;

        public MathOpOrVal(MathOp op)
        {
            Op = op;
        }

        public MathOpOrVal(int value)
        {
            Value = value;
        }

        public override string ToString()
        {
            return (Op != null ? Op.Value.ToString() : Value.Value.ToString());
        }
    }

    internal class TreeNode
    {
        public TreeNode(MathOp op, TreeNode left, TreeNode right)
        {
            Op = op;
            Left = left;
            Right = right;
        }

        public TreeNode(int value)
        {
            Value = value;
        }

        public MathOp? Op;
        public TreeNode Left;
        public TreeNode Right;
        public int? Value;
    }

    internal enum MathOp
    {
        Add,
        Sub,
        Mul,
        Div,
        Mod
    }
}
